package sort.test3_29;

public class QuickSort {


    public  int[] quickSort(int[] nums){
        if (nums.length==0){
            return null;
        }
        sort(nums,0, nums.length-1);

        return  nums;

    }


    public  void sort(int[] nums,int lo,int hi){
        if (lo>=hi){
            return;
        }
        int part = partition(nums, lo, hi);
        //todo:这个中间的分隔部分位置的数字不用再加入到快排中
        sort(nums,lo,part-1);
        sort(nums,part+1,hi);
    }


    public int partition(int[] nums,int lo,int hi){
//       int i=lo;
       int part=nums[lo];
       int j=lo+1;
       int k=hi;
       while (j<k){
           while (nums[j]<part){
               j++;
           }
           while (nums[k]>part){
               k--;
           }
           if (j>=k){
               break;
           }
           swap(nums,j,k);
       }
       swap(nums,lo,k);
       return k;
    }

    public  void  swap(int[] nums,int j,int k){
        int temp = nums[j];
        nums[j]=nums[k];
        nums[k]=temp;
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] a={7,3,5,4,8};
        int[] ints = quickSort.quickSort(a);
        for (int b: ints
             ) {
            System.out.println(b);
        }
    }
}
